Cod sursa(job #1783244)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 18 octombrie 2016 21:34:07
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 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("bmatrix.in");
ofstream fout("bmatrix.out");

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

void rotate() {
    int i,j;
    char b[NMAX][NMAX];
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            b[m-j+1][i]=a[i][j];
    swap(n,m);
    memcpy(a,b,sizeof(b));
}

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 k,i;

	fin>>n>>m;
	for(i=1;i<=n;++i) fin>>(a[i]+1);

	solve();
	rotate();
	solve();

	fout<<rez;

	return 0;
}