Cod sursa(job #840591)

Utilizator stoicatheoFlirk Navok stoicatheo Data 22 decembrie 2012 21:54:52
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>
 
using namespace std;
 
int N, M;
char A[1003][1003];
int H[1003][1003], M1[1003][1003], M2[1003][1003];
 
#define MAX(a, b) ((a > b) ? (a) : (b))
 
int main(int argc, char *argv[]) 
{
    FILE *fi = fopen("bmatrix.in", "r");
    fscanf(fi, "%d %d", &N, &M);
    for (int i(1); i <= N; ++i)
        fscanf(fi, "%s\n", A[i]+1);
    fclose(fi);
 
    for (int i(1); i <= N; ++i)
        for (int j(1); j <= M; ++j)
            if (A[i][j] == '0')
                H[i][j] = H[i-1][j] + 1;
            else
                H[i][j] = 0;
 
    for (int i(1); i <= N; ++i)
        for (int j(1); j <= M; ++j) {
            int max = 0;
            int hmin = 202;
            for (int k = j; k > 0; --k) {
                if (hmin > H[i][k])
                    hmin = H[i][k];
                if (max < (j-k+1) * hmin)
                    max = (j-k+1) * hmin;
            }
            M1[i][j] = max;
            M1[i][M+1] = MAX(M1[i][M+1], MAX(max, M1[i-1][M+1]));
            M1[N+1][j] = MAX(M1[N+1][j], MAX(max, M1[N+1][j-1]));
        }
 
    for (int i = N; i >= 1; --i)
        for (int j = 1; j <= M; ++j)
            if (A[i][j] == '0')
                H[i][j] = H[i+1][j] + 1;
            else
                H[i][j] = 0;
 
    for (int i = N; i >= 1; --i)
        for (int j = M; j >= 1; --j) {
            int max(0);
            int hmin = 202;
            for (int k = j; k <= M; ++k) {
                if (hmin > H[i][k])
                    hmin = H[i][k];
                if (max < (k-j+1) * hmin)
                    max = (k-j+1) * hmin;
            }
            M2[i][j] = max;
            M2[i][0] = MAX(M2[i][0], MAX(max, M2[i+1][0]));
            M2[0][j] = MAX(M2[0][j], MAX(max, M2[0][j+1]));
        }
 
    int R(0);
    for (int j(1); j < M; ++j)
        if (R < M1[N+1][j] + M2[0][j+1])
            R = M1[N+1][j] + M2[0][j+1];
    for (int i(1); i < N; ++i)
        if (R < M1[i][M+1] + M2[i+1][0])
            R = M1[i][M+1] + M2[i+1][0];
 
    ofstream fout("bmatrix.out");
    fout << R << endl;
    fout.close();
 
    return 0;
}