Cod sursa(job #1840733)

Utilizator PondorastiAlex Turcanu Pondorasti Data 4 ianuarie 2017 19:39:26
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,a[255][255],c[255][255],aux[255][255],answer,up[255],down[255],st[255],l[255],r[255];
char s[255];
int Solve(int n, int m);
void Rotate(int &n, int &m);
void dump( int n, int m) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            cerr << a[i][j] << " ";
        }
        cerr << "\n";
    }
}
int Soldier(int a[255],int n);
void GetUpArray(int up[255],int n, int m);
int main() {
    ifstream cin("bmatrix.in");
    ofstream cout("bmatrix.out");
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>s;
        for(int j=1;j<=m;j++) {
            a[i][j]=s[j-1]-'0';}}
    answer=Solve(n,m);
    Rotate(n,m);
    answer=max(Solve(n,m),answer);
    cout<<answer;
    return 0;
}
int Solve(int n, int m) {
    int answer=0;
    GetUpArray(up,n,m);

    Rotate(n,m);
    Rotate(n,m);
    GetUpArray(down,n,m);
    reverse(down+1,down+1+n);
    for(int i=1;i<=n;i++) {
        answer=max(answer,up[i]+down[i+1]);}
    return answer;}
void GetUpArray(int up[255],int n, int m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(a[i][j]==1)
                c[i][j]=0;
            else
                c[i][j]=c[i-1][j]+1;}}
    for(int i=1;i<=n;i++) {
        up[i]=max(up[i-1],Soldier(c[i],m));}}
int Soldier(int a[255],int n) {
    int k;
    st[0]=0;
    k=0;
    ///LEFT
    for(int i=1;i<=n;i++) {
        while(k>0 && a[st[k]]>=a[i]) {
            k--;}
        l[i]=st[k];
        st[++k]=i;}
    k=0;
    st[0]=n+1;
    ///RIGHT
    for(int i=n;i>=1;i--) {
        while(k>0 && a[st[k]]>=a[i]) {
            k--;}
        r[i]=st[k];
        st[++k]=i;}
    int answer=0;
    for(int i=1;i<=n;i++) {
        answer=max(answer,a[i]*(r[i]-l[i]-1));}
    return answer;}
void Rotate(int &n, int &m) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            aux[j][n-i+1]=a[i][j];}}
    swap(n,m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            a[i][j]=aux[i][j];}}}