Cod sursa(job #3161292)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 26 octombrie 2023 15:48:29
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int N, M, up[202][202], D[202], lft[202], rgh[202], maxp1[202], maxp2[202], mx1[202], mx2[202], result;
char A[202][202], B[202][202];
void compute_max(int* best, int* inc){
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			if(A[i][j] == '0')
				up[i][j] = up[i - 1][j] + 1;
			else
				up[i][j] = 0;
	memset(best, 0, sizeof(maxp1));
	for(int i = 1; i <= N; ++i){
		D[0] = 0;
		for(int j = 1; j <= M; ++j){
			while(D[0] && up[i][D[D[0]]] >= up[i][j])
				--D[0];
			if(D[0] == 0)
                lft[j] = j;
			else
                lft[j] = j - D[D[0]];
			D[++D[0]] = j;
		}
		D[0] = 0;
		for(int j = M; j >= 1; --j){
			while(D[0] && up[i][D[D[0]]] >= up[i][j])
				--D[0];
			if(D[0] == 0)
                rgh[j] = M - j + 1;
			else
                rgh[j] = D[D[0]] - j;
			D[++D[0]] = j;
		}
		for(int j = 1; j <= M; ++j)
			if(up[i][j] * (lft[j] + rgh[j] - 1) > best[i])
				best[i] = up[i][j] * (lft[j] + rgh[j] - 1);
	}
	inc[1] = best[1];
	for(int i = 2; i <= N; ++i)
		inc[i] = max(inc[i - 1], best[i]);
}
void do_best(){
	compute_max(maxp1, mx1);
	for(int i = 1; i <= N / 2; ++i)
		for(int j = 1; j <= M; ++j)
			swap(A[i][j], A[N - i + 1][j]);
	compute_max(maxp2, mx2);
	for(int i = 1; i <= N / 2; ++i)
		for(int j = 1; j <= M; ++j)
			swap(A[i][j], A[N - i + 1][j]);
	for(int i = 1; i <= N; ++i)
		if(mx1[i] > 0 && mx2[N - i] > 0)
			result = max(result, mx1[i] + mx2[N - i]);
}
int main(){
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		fin >> A[i];
    for(int i = 1; i <= N; ++i){
        for(int j = M; j >= 1; j-- )
            A[i][j] = A[i][j - 1]; 
    }
	memcpy(B, A, sizeof(B));
	do_best();
	fout << result;
	return 0;
}