Cod sursa(job #3296705)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 15 mai 2025 19:02:48
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");

int v[2005][2005];
int a[2005][2005],sus[2005],jos[2005],n,m,rasp;

void solve(bool stg){
    int sum=0,i,j,k;
	for(i=1;i<=m;i++){
        sus[i]=jos[i]=0;
		for(j=1;j<=n;j++){
            if(stg) a[i][j]=(1-v[i][j])*(a[i-1][j]+1);
            else a[i][j]=(1-v[n-j+1][i])*(a[i-1][j]+1);
		}

	}
	for(i=1;i<=m;i++){
        for(j=i;j<=m;j++){
            sum=0;
            for(k=1;k<=n;k++){
                if(a[j][k]>=j-i+1){
                    sum++;
                    sus[j]=max(sus[j],sum*(j-i+1));
                    jos[i]=max(jos[i],sum*(j-i+1));
                }else sum=0;
            }
        }
        sus[i]=max(sus[i],sus[i-1]);
		jos[m-i+1]=max(jos[m-i+1],jos[m-i+2]);
	}
    for(i=1;i<=m;i++){
        rasp=max(rasp,sus[i]+jos[i+1]);
    }
}



int main(){
    int i,j;char ch;
	cin>>m>>n;
	for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            cin>>ch;v[i][j]=ch-'0';
        }
	}
	solve(1);
	swap(m,n);
	solve(0);
	cout<<rasp;
	return 0;
}