Pagini recente » Cod sursa (job #2667970) | Cod sursa (job #1120283) | Cod sursa (job #859659) | Cod sursa (job #127581) | Cod sursa (job #2696816)
#include <bits/stdc++.h>
#define FASTIO fin.tie(0), fout.tie(0), ios::sync_with_stdio(0)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m, mat[1010][1010], npal[1010][1010], maxarea = 1;
void bruteforce_extend(int i, int j, int& centru, int& last) {
while (last < m && j - (last - j) > 1 && mat[i][j - (last - j) - 1] == mat[i][last + 1])
last++;
npal[i][j] = last - j + 1;
centru = j;
}
void calc_palindromes(int i) {
int centru = 0, last = 0;
for (int j = 1; j <= m; j++) {
if (j > last) {
bruteforce_extend(i, j, centru, last);
} else {
npal[i][j] = min(npal[i][centru - (j - centru)], last - j + 1);
if (j + npal[i][j] - 1 == last && last < m && j - (last - j) > 1 && mat[i][j - (last - j) - 1] == mat[i][last + 1])
bruteforce_extend(i, j, centru, last);
}
}
}
void calc_rectangle(int j) {
int h[n + 2];
h[0] = h[n + 1] = 0;
for (int i = 1; i <= n; i++)
h[i] = npal[i][j];
int left_max_pos[n + 2];
left_max_pos[0] = 0;
int best_pos[n + 2];
int r = -1;
best_pos[++r] = 0;
for (int i = 1; i <= n; i++) {
while (h[i] < h[best_pos[r]])
r--;
if (h[i] == h[best_pos[r]]) {
left_max_pos[i] = left_max_pos[best_pos[r]];
best_pos[r] = i;
} else {
left_max_pos[i] = best_pos[r] + 1;
best_pos[++r] = i;
}
}
int right_max_pos[n + 2];
right_max_pos[n + 1] = 0;
r = -1;
best_pos[++r] = n + 1;
for (int i = n; i >= 1; i--) {
while (h[i] < h[best_pos[r]])
r--;
if (h[i] == h[best_pos[r]]) {
right_max_pos[i] = right_max_pos[best_pos[r]];
best_pos[r] = i;
} else {
right_max_pos[i] = best_pos[r] - 1;
best_pos[++r] = i;
}
}
for (int i = 1; i <= n; i++)
maxarea = max(maxarea, (2 * h[i] - 1) * (right_max_pos[i] - left_max_pos[i] + 1));
}
int main() {
//FASTIO;
fin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> mat[i][j];
for (int i = 1; i <= n; i++)
calc_palindromes(i);
for (int j = 1; j <= m; j++)
calc_rectangle(j);
fout << maxarea;
return 0;
}