Cod sursa(job #819303)

Utilizator antimioritzaUngurul Bulan antimioritza Data 18 noiembrie 2012 19:57:15
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

#define MAXN 300

int N, M;
char A[MAXN][MAXN];

void doSums(int a[MAXN][MAXN]) {
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			if (A[i][j] == '0')
				a[i][j] = a[i - 1][j] + 1;
}

void doMatrix(int best[MAXN]) {
	int a[MAXN][MAXN];
	int left[MAXN], right[MAXN];
	
	memset(a, 0, sizeof(a));
	doSums(a);
	
	for (int i = 1; i <= N; ++i) {
		int coada[MAXN];
		coada[0] = 0;
		
		for (int j = 1; j <= M; ++j) {
			while (coada[0] && a[i][coada[coada[0]]] >= a[i][j])
				--coada[0];
			coada[++coada[0]] = j;
			if (coada[0] == 1)
				left[j] = j;
			else 
				left[j] = j - coada[coada[0] - 1];
		}
		
		coada[0] = 0;
		
		for (int j = M; j >= 1; --j) {
			while (coada[0] && a[i][coada[coada[0]]] >= a[i][j])
				--coada[0];
			coada[++coada[0]] = j;
			if (coada[0] == 1)
				right[j] = M - j + 1;
			else 
				right[j] = coada[coada[0] - 1] - j;
		}
		
		int aux = 0;
		for (int j = 1; j <= M; ++j) 
			aux = max(aux, left[j] * a[i][j] + right[j] * a[i][j] - a[i][j]);
		best[i] = max(best[i - 1], aux);
	}
}

void reverse() {
	for (int i = 1; i <= N / 2; ++i)
		for (int j = 1; j <= M; ++j)
			swap (A[i][j], A[N - i + 1][j]);
}

void solve (int &rez) {
	int max1[MAXN], max2[MAXN];
	
	memset (max1, 0, sizeof(max1));
	memset (max2, 0, sizeof(max2));
	
	doMatrix (max1);
	reverse();
	doMatrix (max2);
	reverse();
	
	for (int i = 1; i < N; ++i)
		rez = max(rez, max1[i] + max2[N - i]);
}

void flip () {
	char a[MAXN][MAXN];
	memcpy (a, A, sizeof(A));
	for (int i = 1; i <= M; ++i)
		for (int j = 1; j <= N; ++j)
			a[i][j] = A[j][i];
	memcpy (A, a, sizeof(a));
	swap (N, M);
}

void read () {
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		fin >> (A[i] + 1);
}

int main () {
	int rez = 0;
	read();
	solve(rez);
	flip();
	solve(rez);
	fout << rez << "\n";
	return 0;
}