Pagini recente » Cod sursa (job #2190115) | Cod sursa (job #6896) | Cod sursa (job #910952) | Cod sursa (job #684739) | Cod sursa (job #2306415)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
void compute(vector<int> &dist, const vector<int> &v, int start, int n, int add) {
vector<int> stk(n + 1, 0);
int sz = 0;
dist[start] = 1;
stk[++sz] = start;
for(int i = start + add; i <= n && i >= 1; i += add) {
while(sz && v[i] <= v[stk[sz]])
sz --;
dist[i] = abs(i - stk[sz]);
stk[++sz] = i;
}
}
int solve(const vector<int> &v, int n) {
vector<int> distoleft(n + 1, 0);
compute(distoleft, v, 1, n, 1);
vector<int> distoright(n + 1, 0);
compute(distoright, v, n, n, -1);
int ans = 0;
for(int i = 1; i <= n; i ++)
ans = max(ans, (distoright[i] + distoleft[i] - 1) * v[i]);
return ans;
}
int main() {
int n, m;
in >> n >> m;
vector<vector<int>> v(n + 1, vector<int> (m + 1, 0));
vector<vector<int>> palmax(m + 2, vector<int> (n + 2, 1));
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++)
in >> v[i][j];
vector<int> p(m + 1, 0);
int r = 1, pos = 1;
p[1] = 1;
for(int j = 2; j <= m; j ++) {
if(r > j)
p[j] = min(r - j + 1, p[2 * pos - j]);
else
p[j] = 1;
while(0 < j - p[j] && j + p[j] <= m && v[i][j - p[j]] == v[i][j + p[j]])
p[j] ++;
if(j + p[j] - 1 > r) {
r = j + p[j] - 1;
pos = j;
}
if(r >= j)
palmax[j][i] = (j - pos) * 2 + 1;
}
}
int ans = 0;
for(int j = 1; j <= m; j ++)
ans = max(ans, solve(palmax[j], n));
out << ans;
return 0;
}