Pagini recente » Cod sursa (job #2758969) | Cod sursa (job #1028358) | Cod sursa (job #1531704) | Cod sursa (job #331998) | Cod sursa (job #1983183)
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
ifstream fin("bmatrix.in"); ofstream fout("bmatrix.out");
const int nmax = 200 + 5;
const int inf = 1 << 30;
int n, m;
bool v[nmax + 1][nmax + 1];
int h[nmax + 1];
pair<int, int> st[nmax + 1];
int sol[ 4 ][nmax + 1];
bool aux[nmax + 1][nmax + 1];
string s;
void rotate_90() {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
aux[ j ][n + 1 - i] = v[ i ][ j ];
}
}
swap(n, m);
memcpy(v, aux, sizeof(v));
}
void solve (int ind) {
memset(h, 0, sizeof(h));
for (int i = 1; i <= n; ++ i) {
int top = 0;
sol[ ind ][ i ] = sol[ ind ][i - 1];
for (int j = 1; j <= m + 1; ++ j) {
if (v[ i ][ j ] == 0 && j <= m) ++ h[ j ];
else h[ j ] = 0;
int s = 0;
while (top > 0 && st[ top ].first >= h[ j ]) {
s += st[ top ].second;
sol[ ind ][ i ] = max(sol[ ind ][ i ], s * st[ top ].first);
-- top;
}
st[ ++ top ] = make_pair(h[ j ], s + 1);
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= n; ++ i) {
fin >> s;
for (int j = 1; j <= m; ++ j) {
v[ i ][ j ] = s[j - 1] - '0';
}
}
for (int i = 0; i < 4; ++ i) {
solve( i );
rotate_90();
}
int ans = 0;
for (int i = 1; i < n; ++ i) {
ans = max(ans, sol[ 0 ][ i ] + sol[ 2 ][n - i]);
}
for (int i = 1; i < m; ++ i) {
ans = max(ans, sol[ 1 ][ i ] + sol[ 3 ][m - i]);
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}