Pagini recente » Cod sursa (job #491278) | Cod sursa (job #1922318) | Cod sursa (job #1342930) | Cod sursa (job #1042597) | Cod sursa (job #1499699)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
template <typename V>
int max_arie_dreptunghi(const int n, V v, const int max_v){
vector<int> st(n, -1), dr(n, -1);
vector<vector<int> > poz(max_v+1);
for(int i = 0; i < n; ++i){
poz[v(i)].push_back(i); }
int rez = 0;
for(int i = max_v; i >= 0; --i){
for(const auto p : poz[i]){
st[p] = dr[p] = p;
if(p > 0 && st[p-1] != -1){
st[p] = st[p-1]; }
if(p < n-1 && st[p+1] != -1){
dr[p] = dr[p+1]; }
st[dr[p]] = st[p];
dr[st[p]] = dr[p];
rez = max(rez, i * (dr[p] - st[p] + 1)); } }
return rez; }
template <typename S, typename R>
void pscpld(const int n, S str, R rez){
int centru = -1, poz_dr = -1;
for(int i = 0; i < n; ++i){
if(i > poz_dr){
int j = 1;
for( ; i-j >= 0 && i+j < n && str(i-j) == str(i+j); ++j);
--j;
rez(i) = j;
if(i+j >= poz_dr){
centru = i;
poz_dr = i+j; } }
else{
const int val_omolog = rez(2*centru - i);
if(i+val_omolog < poz_dr){
rez(i) = val_omolog; }
else{
int j = poz_dr - i + 1;
for( ; i-j >= 0 && i+j < n && str(i-j) == str(i+j); ++j);
--j;
rez(i) = j;
if(i+j >= poz_dr){
centru = i;
poz_dr = i+j; } } } } }
int main(){
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n, m;
f >> n >> m;
vector<vector<int> > v(n, vector<int>(m, 0)),
lung_pal(n, vector<int>(m, 0));
for(auto& x : v){
for(auto& y : x){
f >> y; } }
for(int i = 0; i < n; ++i){
pscpld(m, [&v, i](const int x){ return v[i][x]; },
[&lung_pal, i](const int x)->int&{ return lung_pal[i][x]; }); }
/*
for(const auto x : lung_pal){
for(const auto y : x){
cout << y << ' '; }
cout << endl; }
cout << endl;
*/
int rez = 0;
for(int i = 0; i < m; ++i){
rez = max(rez,
max_arie_dreptunghi(n,
[&lung_pal, i](const int x){ return 2*lung_pal[x][i]+1; },
m)); }
g << rez;
return 0; }