Pagini recente » Cod sursa (job #614704) | Cod sursa (job #2966285) | Cod sursa (job #2725422) | Cod sursa (job #1310026) | Cod sursa (job #635772)
Cod sursa(job #635772)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
#define MAX_N 1010
int n, m, last;
int A[MAX_N][MAX_N], d[MAX_N][MAX_N];
void get_pal() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j == 1) {
d[i][j] = 1;
last = 1;
}
else
d[i][j] = max(min(d[i][last - (j - last)] - 1, last + d[i][last] - j), 1);
int left = j - d[i][j], right = j + d[i][j];
while (0 < left && right <= m && A[i][left] == A[i][right]) {
d[i][j]++;
left--;
right++;
}
if (j + d[i][j] > last + d[i][last])
last = i;
}
}
}
int get_sol() {
int V[MAX_N];
memset(V, 0, sizeof(V));
/* for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
g << d[i][j] << " ";
g << "\n";
}
g << "\n"; */
int ans = 0;
for (int j = 1; j <= m; j++) {
int k = 0;
d[n + 1][j] = 0;
for (int i = 1; i <= n + 1; i++) {
V[++k] = i;
while (d[V[k]][j] <= d[V[k - 1]][j] && k > 1) {
int st = (k > 2) ? V[k - 2] + 1 : 1;
int dr = V[k] - 1;
ans = max(ans, (dr - st + 1) * d[V[k - 1]][j] * 2 - (dr - st + 1));
V[k - 1] = V[k];
V[k--] = 0;
}
/* if (j == 3) {
g << "i = " << i << " : ";
for (int t = 1; t <= k; t++)
g << V[t] << " ";
g << "\n";
} */
}
// g << j << " " << ans << "\n";
}
return ans;
}
int main() {
f >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
f >> A[i][j];
A[i][m + 1] = -1;
}
get_pal();
g << get_sol();
return 0;
}