Нахождение наибольшей нулевой подматрицы

Дана матрица размером . Требуется найти в ней такую подматрицу, состоящую только из нулей, и среди всех таких — имеющую наибольшую площадь (подматрица — это прямоугольная область матрицы).

int n, m;

cin >> n >> m;

vector < vector<int> > a (n, vector<int> (m));

for (int i=0; i<n; ++i)

for (int j=0; j<m; ++j)

cin >> a[i][j];

int ans = 0;

vector<int> d (m, -1), d1 (m), d2 (m);

stack<int> st;

for (int i=0; i<n; ++i) {

for (int j=0; j<m; ++j)

if (a[i][j] == 1)

d[j] = i;

while (!st.empty()) st.pop();

for (int j=0; j<m; ++j) {

while (!st.empty() && d[st.top()] <= d[j]) st.pop();

d1[j] = st.empty()? -1: st.top();

st.push (j);

}

while (!st.empty()) st.pop();

for (int j=m-1; j>=0; --j) {

while (!st.empty() && d[st.top()] <= d[j]) st.pop();

d2[j] = st.empty()? m: st.top();

st.push (j);

}

for (int j=0; j<m; ++j)

ans = max (ans, (i - d[j]) * (d2[j] - d1[j] - 1));

}

cout << ans;

30) Гаусс

const double EPS = 1E-9;

int n;

vector < vector<double> > a (n, vector<double> (n));

... чтение n и a...

double det = 1;

for (int i=0; i<n; ++i) {

int k = i;

for (int j=i+1; j<n; ++j)

if (abs (a[j][i]) > abs (a[k][i]))

k = j;

if (abs (a[k][i]) < EPS) {

det = 0;

break;

}

swap (a[i], a[k]);

if (i!= k)

det = -det;

det *= a[i][i];

for (int j=i+1; j<n; ++j)

a[i][j] /= a[i][i];

for (int j=0; j<n; ++j)

if (j!= i && abs (a[j][i]) > EPS)

for (int k=i+1; k<n; ++k)

a[j][k] -= a[i][k] * a[j][i];

}

cout << det;