Cod sursa(job #2763522)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 14 iulie 2021 18:37:49
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");

static void setmanac(int *v, int *afd, int n) {
  int i,lmost=-1,rmost=-1;
  for(i=0; i<n; i++) {
    int& r=afd[i];
    if(i>rmost)
      r=1;
    else
      r=min(afd[lmost+rmost-i],rmost-i+1);
    while(r<=i && i+r<n && v[i+r]==v[i-r])
      r++;
    r--;
    if(i+r>rmost) {
      rmost=i+r;
      lmost=i-r;
    }
  }
  for(i=0; i<n; i++)
    afd[i]=afd[i]*2+1;
}
static int greatestArea(int *v,int n) {
  #define stack notstacknot
  int i;
  vector<int> stack;
  vector<int> left(n,-1),right(n,n+1);
  
  for(i=0; i<n; i++) {
    while(!stack.empty() && v[stack.back()]>=v[i])
      stack.pop_back();
    if(stack.size())
      left[i]=stack.back();
    stack.push_back(i);
  }
  stack=vector<int>();
  for(i=n-1; i>=0; i--) {
    while(!stack.empty() && v[stack.back()]>=v[i])
      stack.pop_back();
    if(stack.size())
      right[i]=stack.back();
    stack.push_back(i);
  }
  int maxx=0;
  for(i=0; i<n; i++) {
    maxx=max((right[i]-left[i]-1)*v[i],maxx);
  }
  #undef stack
  return maxx;
}

int mat[1000][1000];
int manac[1000][1000];
int temp[1001];

int n,m;

int main() {
  int i,j;
  int maxx;
  
  cin >> n >> m;  
  for(i=0; i<n; i++) {
    for(j=0; j<m; j++) {
      cin >> mat[i][j];
    }
    setmanac(mat[i],manac[i],m);
    //for(j=0; j<m; j++) {
      //cout << manac[i][j] <<' ';
    //}
    //cout << '\n';
  }
  maxx=0;
  for(i=0; i<m; i++) {
    for(j=0; j<n; j++)
      temp[j]=manac[j][i];
    maxx=max(maxx,greatestArea(temp,n));
  }
  cout << maxx << '\n';
}