#include "soccer.h"
#include <iostream>
#include <algorithm>
#define pii std::pair<int, int>
#define printf
struct entry_t
{
int l, r, c;
};
#define MAXN 300
std::vector<entry_t> info[MAXN+5][MAXN+5];
void compress_entvec(std::vector<entry_t> &ref)
{
std::sort(ref.begin(), ref.end(), [](const entry_t &a, const entry_t &b){ return pii(a.l, a.r) < pii(b.l, b.r); });
int del = 0;
for (int i = 1; i < ref.size(); ++i)
{
if (ref[i].l == ref[i-del-1].l && ref[i].r == ref[i-del-1].r)
{
ref[i-del-1].c = std::max(ref[i-del-1].c, ref[i].c);
++del;
}
else
ref[i-del] = ref[i];
}
ref.resize(ref.size()-del);
}
void push_continuation(std::vector<entry_t> &dest, std::vector<entry_t> &src, std::vector<entry_t> &nex)
{
for (int i = 0; i < src.size(); ++i)
{
entry_t &c_src = src[i];
for (int j = 0; j < nex.size(); ++j)
{
entry_t &c_nex = nex[j];
entry_t new_entry = { .l = std::max(c_nex.l, c_src.l), .r = std::min(c_nex.r, c_src.r) };
new_entry.c = c_src.c + new_entry.r - new_entry.l + 1;
if (new_entry.l > new_entry.r)
continue;
printf(" src: %i-%i, c=%i, nex: %i-%i, result: %i-%i, c=%i\n", c_src.l, c_src.r, c_src.c, c_nex.l, c_nex.r, new_entry.l, new_entry.r, new_entry.c);
dest.push_back(new_entry);
}
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
for (int i = 0; i < N; ++i)
{
printf("row %i...\n", i);
pii cur(-1, -1);
for (int j = 0; j < N; ++j)
{
if (F[i][j] == 0)
{
if (cur.first == -1)
cur = pii(j, j-1);
++cur.second;
}
if (cur.first != -1 && (j == N-1 || F[i][j+1] == 1))
{
info[i][i].push_back((entry_t){ .l = cur.first, .r = cur.second, .c = cur.second-cur.first+1 });
printf(" has %i-%i, c=%i\n", cur.first, cur.second, info[i][i].back().c);
cur = pii(-1, -1);
}
}
}
for (int l = 2; l <= N; ++l)
{
for (int i = 0; i <= N-l; ++i)
{
printf("push continution: %i-%i -> %i-%i\n", i, i+l-2, i, i+l-1);
push_continuation(info[i][i+l-1], info[i][i+l-2], info[i+l-1][i+l-1]);
printf("push continution: %i-%i -> %i-%i\n", i+1, i+l-1, i, i+l-1);
push_continuation(info[i][i+l-1], info[i+1][i+l-1], info[i][i]);
compress_entvec(info[i][i+l-1]);
}
}
int res = 0;
for (int i = 0; i < N; ++i)
for (int j = i; j < N; ++j)
for (int l = 0; l < info[i][j].size(); ++l)
res = std::max(res, info[i][j][l].c);
return res;
}
