Pagini recente » Cod sursa (job #29617) | Cod sursa (job #1032911) | Cod sursa (job #490455) | Cod sursa (job #2146118) | Cod sursa (job #1518560)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int bf_extend(vector < int> const &V, int i, int dist) {
int j;
for(j = dist; 1 <= i - j && i + j < V.size() && V[i + j] == V[i - j]; j++);
return j - 1;
}
vector < int > manacher(vector < int > const &V) {
vector < int > len(V.size(), 0);
int i, j, r, ir;
for(i = 1, r = ir = -1; i < V.size(); i++) {
if(i > r) {
len[i] = bf_extend(V, i, 1);
}
else {
if(i + len[2*ir - i] < r) {
len[i] = len[2*ir - i];
}
else {
len[i] = bf_extend(V, i, r - i + 1);
}
}
}
return len;
}
int get_area_column(vector < int > const &col) {
vector < int > l(col.size()), r(col.size());
stack < int > s;
int i, amax = 0;
/*for(i = 1; i < col.size(); i++) out << col[i] << ' ';
out << '\n';*/
for(i = 1; i < col.size(); i++) {
while(!s.empty() && col[i] < col[s.top()]) {
r[s.top()] = i;
s.pop();
}
s.push(i);
}
while(!s.empty()) {
r[s.top()] = col.size();
s.pop();
}
for(i = col.size() - 1; i; i--) {
while(!s.empty() && col[i] < col[s.top()]) {
l[s.top()] = i;
s.pop();
}
s.push(i);
}
while(!s.empty()) {
l[s.top()] = 0;
s.pop();
}
for(i = 1; i < col.size(); i++) {
amax = max(amax, (2*col[i] + 1) * (r[i] - l[i] - 1));
}
return amax;
}
int get_area_whole(const int n, const int m, vector < vector < int > > const &len) {
vector < int > col;
int amax = 0, i, j;
for(i = 1; i <= m; i++) {
col.clear();
col.push_back(0);
for(j = 1; j <= n; j++) {
col.push_back(len[j][i]);
}
//out << get_area_column(col) << '\n';
amax = max(amax, get_area_column(col));
}
return amax;
}
int main() {
int n, m, i, j;
in >> n >> m;
vector < vector < int > > a(n + 1), len(n + 1);
for(i = 1; i <= n; i++) {
a[i].resize(m + 1);
len[i].resize(m + 1);
for(j = 1; j <= m; j++) {
in >> a[i][j];
}
len[i] = manacher(a[i]);
}
/*for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
out << len[i][j] << ' ';
}
out << '\n';
}*/
out << get_area_whole(n, m, len) << '\n';
return 0;
}