Cod sursa(job #2571176)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 4 martie 2020 21:27:14
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int linsus[N],linjos[N],linst[N],lindr[N];
char mat[N][N];
int stv[N];
int st[N];
char aux[N][N];
int skyline(int v[],int n){
  int vf=0;
  stv[0]=0;
  for(int i=1;i<=n;i++){
    while(vf>0 && v[i]<=v[stv[vf]])
      vf--;
    st[i]=stv[vf];
    stv[++vf]=i;
  }
  int ans=0;
  vf=0;
  stv[vf]=n+1;
  for(int i=n;i>=1;i--){
    while(vf>0 && v[i]<=v[stv[vf]])
      vf--;
    int dr=stv[vf];
    ans=max(ans,(dr-st[i]-1)*v[i]);
    stv[++vf]=i;
  }
  return ans;
}
int rot(int &n,int &m){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      aux[j][n-i+1]=mat[i][j];
    }
  }
  swap(n,m);
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      mat[i][j]=aux[i][j];
    }
  }
}
int val[N];
void solve(int lin[],int n,int m){
  for(int i=1;i<=m;i++)
    val[i]=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(mat[i][j]==0)
        val[j]++;
      else
        val[j]=0;
    }
    lin[i]=skyline(val,m);
  }
  for(int i=1;i<=n;i++){
    lin[i]=max(lin[i],lin[i-1]);
  }
}

int main()
{
  FILE*fin,*fout;
  fin=fopen("bmatrix.in","r");
  fout=fopen("bmatrix.out","w");
  int n,m;
  fscanf(fin,"%d%d ",&n,&m);
  for(int i=1;i<=n;i++){
    fgets(mat[i]+1,N,fin);
    for(int j=1;j<=m;j++)
      mat[i][j]-='0';
  }
  solve(linsus,n,m);
  rot(n,m);
  solve(linst,n,m);
  rot(n,m);
  solve(linjos,n,m);
  rot(n,m);
  solve(lindr,n,m);
  swap(n,m);
  int ans=0;
  for(int i=1;i<=n;i++){
    ans=max(ans,linsus[i]+linjos[n-i]);
  }
  for(int i=1;i<=m;i++){
    ans=max(ans,linst[i]+lindr[m-i]);
  }
  fprintf(fout,"%d",ans);
  return 0;
}