Pagini recente » Cod sursa (job #817170) | Cod sursa (job #984327) | Cod sursa (job #1308754) | Cod sursa (job #1880428) | Cod sursa (job #2316752)
#include <fstream>
#include <stack>
using namespace std;
int main() {
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int n, m;
in >> n >> m;
int a[n][m], v[n][m];
for (int k = 0; k < n; k ++) {
for (int i = 0; i < m; i++) {
in >> a[k][i];
}
//Manacher
int j, centru = 0, dr = 0;
for (int i = 0; i < m; i++) {
if (dr <= i) {
v[k][i] = 1;
j = 1;
while (i - j >= 0 && i + j < m && a[k][i - j] == a[k][i + j]) {
j++;
v[k][i]++;
}
dr = i + j - 1;
centru = i;
} else {
v[k][i] = min(dr - i + 1, v[k][2 * centru - i]);
if (v[k][i] + i >= dr) {
j = v[k][i];
while (i - j >= 0 && i + j < m && a[k][i - j] == a[k][i + j]) {
j++;
v[k][i]++;
}
dr = i + j - 1;
centru = i;
}
}
}
}
//Skyline
int sol = 0;
for (int j = 0; j < m; j ++) {
stack <int> s, first;
int p[n];
for (int i = 0; i < n; i ++) {
while (!s.empty() && s.top() > v[i][j]) {
s.pop();
first.pop();
}
if (s.empty()) {
s.push(v[i][j]);
first.push(0);
} else if (s.top() < v[i][j]) {
s.push(v[i][j]);
first.push(i);
}
p[i] = (2 * s.top() - 1) * (i - first.top() + 1);
}
while(!s.empty()) {
s.pop();
}
while(!first.empty()) {
first.pop();
}
for (int i = n - 1; i >= 0; i --) {
while (!s.empty() && s.top() > v[i][j]) {
s.pop();
first.pop();
}
if (s.empty()) {
s.push(v[i][j]);
first.push(n - 1);
} else if (s.top() < v[i][j]) {
s.push(v[i][j]);
first.push(i);
}
int x = (2 * s.top() - 1) * (first.top() - i + 1);
p[i] = max(x, p[i]);
if (p[i] > sol) {
sol = p[i];
}
}
}
out << sol;
return 0;
}