Cod sursa(job #3180030)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 4 decembrie 2023 15:58:50
Problema BMatrix Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 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];
int taken[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;
        }
    }
}

bool isInRect(int i, int j, rect _rect) {
    return i >= _rect.i1 && i <= _rect.i2 && j >= _rect.j1 && j <= _rect.j2;
}

void placeRect(rect _rect) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            taken[i][j] = taken[i][j - 1] + taken[i - 1][j] - taken[i - 1][j - 1];
            if (isInRect(i, j, _rect)) {
                taken[i][j]++;
            }
        }
    }
}

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;
                    continue;
                }

                int alreadyTaken = taken[i2][j] - taken[i1 - 1][j] - taken[i2][start - 1] + taken[i1 - 1][start - 1];

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

int main()
{
    char s;

    fin >> n >> m;

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

    initLengths();

    answer += solve();

    placeRect(firstRect);

    answer += solve();

    fout << answer;
}