Pagini recente » Cod sursa (job #2787924) | Cod sursa (job #1350500) | Cod sursa (job #1879355) | Statistici Codrut-Andrei (clmai) | Cod sursa (job #1992987)
#include <fstream>
#include <stack>
using namespace std;
ifstream cin ("bmatrix.in");
ofstream cout ("bmatrix.out");
char sir[205];
int A[205][205];
int aux[205][205];
int h[205][205];
int l[205][205];
int up[205];
int down[205];
int st[205];
int dr[205];
int oriz[205];
int vert[205];
stack <int> lft;
stack <int> rgt;
void intors (int m, int n){
for (int i=1; i<=m; i++){
for (int j=1; j<=n; j++){
aux[n-j+1][i] = A[i][j];
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
A[i][j] = aux[i][j];
}
}
return;
}
int main()
{
int m, n;
cin>>m>>n;
for (int i=1; i<=m; i++){
cin>>(sir+1);
for (int j=1; j<=n; j++){
A[i][j]=sir[j]-'0';
}
}
for (int i=1; i<=m; i++){
for (int j=1; j<=n; j++){
if (A[i][j] == 0){
h[i][j] = h[i-1][j] + 1;
}
if (A[i][j] == 1) {
h[i][j] = 0;
}
}
}
for (int i=m; i>=1; i--){
for (int j=1; j<=n; j++){
if (A[i][j] == 0){
l[i][j] = l[i+1][j] + 1;
}
else {
l[i][j] = 0;
}
}
}
for (int k=1; k<=m; k++){
while (!lft.empty()){
lft.pop();
}
while (!rgt.empty()){
rgt.pop();
}
lft.push(0);
rgt.push(n+1);
for (int j=1; j<=n; j++){
while (h[k][j] <= h[k][lft.top()] && lft.size()>1){
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=n; j>=1; j--){
while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1){
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=n; j++){
up[j]=max(up[j-1], h[k][j] * (dr[j] - st[j] -1));
}
//up done
while (!lft.empty()){
lft.pop();
}
while (!rgt.empty()){
rgt.pop();
}
lft.push(0);
rgt.push(n+1);
for (int j=1; j<=n; j++){
while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1){
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=n; j>=1; j--){
while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1){
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=n; j++){
down[j]=max(down[j-1], l[k+1][j] * (dr[j] - st[j] -1));
}
//down done
oriz[k]=max(oriz[k-1], up[n] + down[n]);
}
intors(m,n);
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (A[i][j] == 0){
h[i][j] = h[i-1][j] + 1;
}
if (A[i][j] == 1) {
h[i][j] = 0;
}
}
}
for (int i=n; i>=1; i--){
for (int j=1; j<=m; j++){
if (A[i][j] == 0){
l[i][j] = l[i+1][j] + 1;
}
else {
l[i][j] = 0;
}
}
}
for (int k=1; k<=n; k++){
while (!lft.empty()){
lft.pop();
}
while (!rgt.empty()){
rgt.pop();
}
lft.push(0);
rgt.push(m+1);
for (int j=1; j<=m; j++){
while (h[k][j] <= h[k][lft.top()] && lft.size()>1){
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=m; j>=1; j--){
while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1){
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=m; j++){
up[j]=max(up[j-1], h[k][j] * (dr[j] - st[j] -1));
}
//up done
while (!lft.empty()){
lft.pop();
}
while (!rgt.empty()){
rgt.pop();
}
lft.push(0);
rgt.push(m+1);
for (int j=1; j<=m; j++){
while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1){
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=m; j>=1; j--){
while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1){
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=m; j++){
down[j]=max(down[j-1], l[k+1][j] * (dr[j] - st[j] -1));
}
//down done
vert[k]=max(vert[k-1], up[m] + down[m]);
}
cout<<max(oriz[m],vert[n])<<'\n';
return 0;
}