Cod sursa(job #2694956)

Utilizator kywyPApescu tiGEriu kywy Data 11 ianuarie 2021 10:07:27
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
#define DIM 205
 
using namespace std;
 
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
int N,M,a[DIM][DIM],sol,sus[DIM],jos[DIM];
char s[DIM][DIM],b[DIM][DIM];
void rotate(){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            b[M-j+1][i]=s[i][j];
    swap(N,M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            s[i][j]=b[i][j];
}
void solve(){
    int nr;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++)
            if(s[i][j]=='0')
                a[i][j]=a[i-1][j]+1;
            else
                a[i][j]=0;
        sus[i]=jos[i]=0;
    }
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j++){
                nr=0;
            for(int k=1;k<=M;k++){
                if(a[j][k]>=j-i+1)
                    nr++;
                else
                    nr=0;
                int aria=nr*(j-i+1);
                sus[j]=max(sus[j],aria);
                jos[i]=max(jos[i],aria);
            }
        }
    for(int i=2;i<=N;i++)
        sus[i]=max(sus[i-1],sus[i]);
    for(int i=N-1;i>=1;i--)
        jos[i]=max(jos[i+1],jos[i]);
    for(int i=1;i<N;i++)
        sol=max(sol,sus[i]+jos[i+1]);
}
int main(){
    in>>N>>M;
    for(int i=1;i<=N;i++)
        in>>s[i]+1;
    solve();
    rotate();
    solve();
    out<<sol<<"\n";
    return 0;
}