Cod sursa(job #3179735)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 4 decembrie 2023 08:12:09
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

struct rect{
    int i1;
    int j1;
    int i2;
    int j2;
};

int n, m;
bool matrix[201][201];
int lengths[201][201];
rect firstRect;
int answer;

void initLengths(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(matrix[i][j] == 1)
                lengths[i][j] = 0;
            else
                lengths[i][j] = lengths[i - 1][j] + 1;
        }
    }
}

int solve(){
    int maxSize = 0;
    for(int i2 = 1; i2 <= n; i2++){
        for(int i1 = 1; i1 <= i2; i1++){
            int start = 1;
            int length = 0;
            for(int j = 1; j <= m; j++){
                if(lengths[i2][j] == i2 - i1 + 1){
                    length++;
                }
                else{
                    length = 0;
                    start = j + 1;
                }

                if(maxSize < length * (i2 - i1 + 1)){
                    maxSize = length * (i2 - i1 + 1);
                    firstRect.i1 = i1;
                    firstRect.i2 = i2;
                    firstRect.j1 = start;
                    firstRect.j2 = j;
                }
            }
        }
    }
    return maxSize;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> matrix[i][j];
        }
    }

    initLengths();

    answer += solve();

    for(int i = firstRect.i1; i <= firstRect.i2; i++){
        for(int j = firstRect.j1; j <= firstRect.j2; j++){
            matrix[i][j] = true;
        }
    }

    initLengths();

    answer += solve();

    fout << answer;

}