Pagini recente » Cod sursa (job #2025927) | Cod sursa (job #852031) | Cod sursa (job #2045300) | Cod sursa (job #1726140) | Cod sursa (job #2786040)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m, ans, v[1005][1005], manacher[1005][1005];
int aux[1005], st[1005], dr[1005], stiva[1005];
void compute_manacher(int ind);
void solve(int ind);
int main() {
fin >> n >> m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
fin >> v[i][j];
}
}
for (int i=1;i<=n;i++){
compute_manacher(i);
}
for (int i=1;i<=m;i++){
solve(i);
}
fout << ans << '\n';
return 0;
}
void solve(int ind) {
for (int i=1;i<=n;i++)
aux[i] = manacher[i][ind], st[i] = dr[i] = 0;
int nr;
for (int i=1;i<=n;i++){
if (i == 1){
nr = 1;
stiva[1] = 1;
}else{
while(nr && aux[i] < aux[stiva[nr]]){
dr[stiva[nr]] = i;
nr --;
}
stiva[++nr] = i;
}
}
for (int i=1;i<=nr;i++)
dr[stiva[i]] = n + 1;
for (int i=n;i>=1;i--){
if (i == n){
nr = 1;
stiva[1] = n;
}else{
while(nr && aux[i] < aux[stiva[nr]]){
st[stiva[nr]] = i;
nr --;
}
stiva[++nr] = i;
}
}
for (int i=1;i<=n;i++){
int latime = dr[i] - st[i] - 1;
int lungime = aux[i] * 2 - 1;
ans = max(ans, latime * lungime);
}
}
void compute_manacher(int ind) {
int l = 0, r = 0;
for (int i=1;i<=m;i++){
int k;
if (i > r)
k = 1;
else
k = min(manacher[ind][l+r-i], r-i+1);
while(i-k>=1 && i+k<=m && v[ind][i-k] == v[ind][i+k]){
k ++;
}
manacher[ind][i] = k;
k --;
if (i + k > r){
l = i - k;
r = i + k;
}
}
}