Cod sursa(job #1783457)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 19 octombrie 2016 00:10:47
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#define MOD 800013
#define pb push_back
#define INF 0x3f3f3f3f
#define ll long long
#define NMAX 205

using namespace std;

typedef pair<int, int> pii;

//ifstream fin("fisier.in");
FILE *fin=fopen("bmatrix.in","r");
//ofstream fout("bmatrix.out");
FILE *fout=fopen("bmatrix.out","w");

int amax[NMAX][NMAX],sp[NMAX][NMAX],aux[NMAX][NMAX],n,m,rez;
char a[NMAX][NMAX];

void solve() {
	int i,j,k,vmin;

	for(i=1;i<=n;++i) {
		for(j=1;j<=m;++j) {
			if(a[i][j]=='0') sp[i][j]=sp[i][j-1]+1;
			else sp[i][j]=0;

			amax[i][j]=0;
		}
	}
	for(i=1;i<=n;++i) {
		for(j=1;j<=m;++j) {
			vmin=INF;
			for(k=1;i-k+1>0;++k) {
				vmin=min(vmin,sp[i-k+1][j]);
				amax[i][k]=max(max(max(vmin*k,amax[i][k-1]),amax[i][k]),amax[i-1][k-1]);
			}
		}
	}
	for(i=1;i<n;++i) rez=max(rez,amax[i][i]+amax[n][n-i]);
}

int main() {
	int j,i;

	fscanf(fin,"%d%d\n",&n,&m);
	for(i=1;i<=n;++i) fgets(a[i]+1,NMAX,fin);

	solve();

	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			aux[m-j+1][i]=a[i][j];
	swap(n,m);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j) a[i][j]=aux[i][j];

	solve();

	fprintf(fout,"%d",rez);

	return 0;
}