Pagini recente » Cod sursa (job #173837) | Cod sursa (job #1989568) | Istoria paginii runda/cnitv_gimnaziu_1/clasament | Cod sursa (job #1473325) | Cod sursa (job #2253940)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int NMAX = 205;
int v[NMAX][NMAX], aux[NMAX][NMAX];
int lineup[NMAX], linedown[NMAX], colup[NMAX], coldown[NMAX];
void solve(int n, int m, int *d) {
for(int i = 1; i <= n; i ++) {
vector<int> a(m + 1, 0);
for(int j = 1; j <= m; j ++) {
int k = i;
while(k >= 1 && v[k][j] == 0) {
a[j] ++;
k --;
}
}
vector<int> stk(m + 1, 0);
int sz = 0;
int maxim = 0;
stk[++sz] = 0;
a[0] = INT_MIN;
for(int j = 1; j <= m; j ++) {
while(sz > 0 && a[stk[sz]] >= a[j])
sz --;
int pretender = (j - stk[sz]) * a[j];
maxim = max(pretender, maxim);
stk[++sz] = j;
}
d[i] = max(d[i - 1], maxim);
}
}
void rotatematrix(int n, int m) {
memcpy(aux, v, sizeof(v));
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
v[j][n - i + 1] = aux[i][j];
}
int main() {
int n, m;
in >> n >> m;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
char c;
in >> c;
v[i][j] = c - '0';
}
}
solve(n, m, lineup);
rotatematrix(n, m);
solve(m, n, colup);
rotatematrix(m, n);
solve(n, m, linedown);
rotatematrix(n, m);
solve(m, n, coldown);
int ans = 0;
for(int i = 1; i < n; i ++)
ans = max(ans, lineup[i] + linedown[n - (i + 1) + 1]);
for(int i = 1; i < m; i ++)
ans = max(ans, colup[i] + coldown[m - (i + 1) + 1]);
out << ans;
return 0;
}