Cod sursa(job #824718)

Utilizator toranagahVlad Badelita toranagah Data 26 noiembrie 2012 21:21:38
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int MAX_N = 300;
bool m[MAX_N][MAX_N];
int N, M, sol;
void read(); 
void solve();
void find_mat(int rez[]);
void change_direction();
void rotate();
void print(); 
void debug();

int main() {
    read();
    solve();
    rotate();
    solve();
    print();
    return 0;
}

void debug() {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cerr << m[i][j] << ' ';
        }
        cerr << endl;
    }
    cerr << endl;
}

void read() {
    string line;
    fin >> N >> M;
    getline(fin, line);
    for (int i = 1; i <= N; ++i) {
        getline(fin, line);
        for (int j = 1; j <= M; ++j) {
            m[i][j] = line[j-1] - '0';
        }
    }
}

void solve() {
    int rez1[MAX_N], rez2[MAX_N];
    memset(rez1, 0, sizeof(rez1));
    memset(rez2, 0, sizeof(rez2));
    //debug();
    find_mat(rez1);
    change_direction();
    //debug();
    find_mat(rez2);
    change_direction();
    for (int i = 1; i < N; ++i) {
        sol = max(sol, rez1[i] + rez2[N-i]);
        //cerr << rez1[i] << ' ' << rez2[N-i] << endl;
    }
    //cerr << sol << endl;
} 

struct col {int h, pos;};
void find_mat(int rez[]) {
    col st[MAX_N];
    int stTop = 0;
    int row[MAX_N];
    for (int i = 0; i <= M; ++i) row[i] = 0;
    for (int i = 1; i <= N; ++i) {
        row[M+1] = 0;
        for (int j = 1; j <= M + 1; ++j) {
            if (m[i][j] == false) {
                ++row[j];
            } else {
                row[j] = 0;
            }
            int p = j;
            while (stTop > 0 && row[j] <= st[stTop].h) {
                rez[i] = max(rez[i], st[stTop].h * (j - st[stTop].pos));
                p = st[stTop].pos;
                --stTop;
            }
            st[++stTop].h = row[j];
            st[stTop].pos = p;
            //cerr << st[stTop].h << ' ' << st[stTop].pos << endl;
        }
        rez[i] = max(rez[i], rez[i-1]);
        //cerr << rez[i] << endl;
    }
}

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

void rotate() {
    bool temp[MAX_N][MAX_N];
    memcpy(temp, m, sizeof(m));
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= N; ++j) {
            temp[i][j] = m[j][i];
        }
    }
    memcpy(m, temp, sizeof(temp));
    swap(N, M);
}

void print() {
    cerr << sol;
    fout << sol;
}