Pagini recente » Cod sursa (job #1088902) | Cod sursa (job #814382) | Cod sursa (job #2947038) | Cod sursa (job #585898) | Cod sursa (job #2096647)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
void Complete(int n, int m, vector < vector < char > > &mat,
vector < vector < int > > &v, vector < vector < int > > &prop) {
stack < int > stk;
for (int i = 1; i <= n; i ++) {
stk.push(0);
mat[i][0] = '$';
for (int j = 1; j <= m; j ++) {
while ((mat[i][stk.top()] == mat[i][j]) and
(prop[i][stk.top()] >= prop[i][j])) {
stk.pop();
}
v[i][j] = stk.top() + 1;
stk.push(j);
}
}
}
int Solve(int n, int m, vector < vector < char > > &mat) {
vector < vector < int > > up(n + 1, vector < int > (m + 1, 1)),
down(n + 1, vector < int > (m + 1, 1));
for (int i = 2; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (mat[i][j] == mat[i - 1][j]) {
up[i][j] = up[i - 1][j] + 1;
}
}
}
for (int i = n - 1; i >= 0; i --) {
for (int j = 1; j <= m; j ++) {
if (mat[i][j] == mat[i + 1][j]) {
down[i][j] = down[i + 1][j] + 1;
}
}
}
vector < vector < int > > st_up(n + 1, vector < int > (m + 1)),
st_down(n + 1, vector < int > (m + 1));
Complete(n, m, mat, st_up, up);
Complete(n, m, mat, st_down, down);
vector < int > best_up(n + 1), best_down(n + 1);
int previous = 0;
for (int i = 1; i <= n; i ++) {
int best = 0;
for (int j = 1; j <= m; j ++) {
if (mat[i][j] != '0') {
continue;
}
best = max(best, (j - st_up[i][j] + 1) * up[i][j]);
}
previous = max(best, previous);
best_up[i] = previous;
}
previous = 0;
for (int i = n; i >= 1; i --) {
int best = 0;
for (int j = 1; j <= m; j ++) {
if (mat[i][j] != '0') {
continue;
}
best = max(best, (j - st_down[i][j] + 1) * down[i][j]);
}
previous = max(best, previous);
best_down[i] = previous;
}
int ans = 0;
for (int i = 1; i < n; i ++) {
ans = max(ans, best_up[i] + best_down[i + 1]);
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
vector < vector < char > > mat1(n + 1, vector < char > (m + 1)),
mat2 (m + 1, vector < char > (n + 1));
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> mat1[i][j];
}
}
for (int j = 1; j <= m; j ++) {
for (int i = n; i >= 1; i --) {
mat2[j][n - i + 1] = mat1[i][j];
}
}
int ans1 = Solve(n, m, mat1);
int ans2 = Solve(m, n, mat2);
cout << max(ans1, ans2) << '\n';
}