Pagini recente » Borderou de evaluare (job #479076) | Borderou de evaluare (job #1487788) | Cod sursa (job #3279758) | Borderou de evaluare (job #1669770) | Cod sursa (job #2763522)
#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';
}