Pagini recente » Cod sursa (job #2500502) | Cod sursa (job #2046941) | Cod sursa (job #72162) | Cod sursa (job #151903) | Cod sursa (job #2037088)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
bool is_good(int i, int cnt, int m) {
return i + cnt <= m and i - cnt >= 1;
}
void fill_pali(vector < int > &pali, vector < int > &v, int m) {
int poz = -1;
int max_r = -1;
for (int i = 1; i <= m; i ++) {
int cnt = 0;
if (i >= max_r) {
while (is_good(i, cnt, m)) {
if (v[i + cnt] == v[i - cnt]) {
cnt ++;
continue;
}
break;
}
cnt --;
pali[i] = cnt * 2 + 1;
poz = i;
max_r = i + cnt;
continue;
}
int k = pali[2 * poz - i];
if (i + k < max_r) {
pali[i] = k;
continue;
}
cnt = max_r - i + 1;
while (is_good(i, cnt, m)) {
if (v[i + cnt] == v[i - cnt]) {
cnt ++;
continue;
}
break;
}
cnt --;
pali[i] = cnt * 2 + 1;
poz = i;
max_r = i + cnt;
}
}
int main(int argc, char const *argv[]) {
int n, m;
cin >> n >> m;
vector < vector < int > > mat(n + 1, vector < int > (m + 7));
for (int i = 1 ; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> mat[i][j];
}
}
vector < vector < int > > pali(n + 7, vector < int > (m + 7));
for (int i = 1; i <= n; i ++) {
fill_pali(pali[i], mat[i], m);
}
stack < int > st;
vector < vector < int > > up(n + 7, vector < int > (m + 7));
vector < vector < int > > dw(n + 7, vector < int > (m + 7));
for (int j = 1; j <= m; j ++) {
pali[0][j] = -1;
pali[n + 1][j] = -1;
st.push(0);
for (int i = 1; i <= n; i ++) {
if (pali[st.top()][j] >= pali[i][j]) {
while (pali[st.top()][j] >= pali[i][j]) {
st.pop();
}
up[i][j] = st.top() + 1;
st.push(i);
}
else {
up[i][j] = i;
st.push(i);
}
}
while (!st.empty()) {
st.pop();
}
st.push(n + 1);
for (int i = n; i >= 1; i --) {
if (pali[st.top()][j] >= pali[i][j]) {
while (pali[st.top()][j] >= pali[i][j]) {
st.pop();
}
dw[i][j] = st.top() - 1;
st.push(i);
}
else {
dw[i][j] = i;
st.push(i);
}
}
while (!st.empty()) {
st.pop();
}
}
int sol = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
int cur = pali[i][j] * (dw[i][j] - up[i][j] + 1);
sol = max(sol, cur);
}
}
cout << sol << '\n';
}